package com.liwt.algorithm.pattern;

/**
 * KMP算法的Java实现例子与测试、分析
 * 
 * @author likebamboo
 * @create 2013-10-15
 * @see http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
 * 
 */

public class KMP {

	/**
	 * 对子串加以预处理，从而找到匹配失败时子串回退的位置 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
	 * 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
	 * 
	 * @param sub
	 *            待处理的子串
	 * @return
	 */
	public static int[] next(String sub) {
		char[] c = sub.toCharArray();
		int length = sub.length();
		int[] p = new int[length];
		p[0] = 0;
		int j = 0;
		// 每循环一次，就会找到一个回退位置
		for (int i = 1; i < length; i++) {
			// 当找到第一个匹配的字符时，即j>0时才会执行这个循环
			// 或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
			// p1
			while (j > 0 && c[j] != c[i]) {
				j = p[j];
			}
			// p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
			if (c[j] == c[i]) {
				j++;
			}
			// 找到一个回退位置j，把其放入P[i]中
			p[i] = j;
		}
		return p;
	}

	/**
	 * KMP实现
	 * 
	 * @param parStr
	 * @param subStr
	 * @return
	 */

	public static void kmp(String parStr, String subStr) {
		int subSize = subStr.length();
		int parSize = parStr.length();
		char[] A = parStr.toCharArray();
		char[] B = subStr.toCharArray();
		int[] P = next(subStr);
		int j = 0;
		int k = 0;
		for (int i = 0; i < parSize; i++) {
			// 当找到第一个匹配的字符时，即j>0时才会执行这个循环
			// 或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
			// p1
			while (j > 0 && B[j] != A[i]) {
				// 找到合适的回退位置
				j = P[j - 1];
			}
			// p2 找到一个匹配的字符
			if (B[j] == A[i]) {
				j++;
			}
			// 输出匹配结果，并且让比较继续下去
			if (j == subSize) {
				j = P[j - 1];
				k++;
				System.out.printf("Find subString '%s' at %d\n", subStr, i
						- subSize + 1);
			}
		}

		System.out.printf("Totally found %d times for '%s'.\n\n", k, subStr);

	}

	public static void main(String[] args) {
		// next数组为P[0, 0, 0 , 0, 1, 2, 0]
		kmp("BBC ABCDAB ABCDABCDABDE", "ABCDABD");
		// next数组为P[0, 0, 1, 2, 3, 4]
		kmp("Test ititi ititit! Test ititit!这个会匹配2次", "ititit");
		// next数组为P[0, 0, 0]
		kmp("测试汉字的匹配，崔卫兵。这个会匹配1次", "崔卫兵");
		// next数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
		kmp("这个会匹配0次", "it1it1it1");
	}
}